﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Kamisado
{
    public partial class Form1 : Form
    {
        class Monk
        {
            public int X;
            public int Y;
            public Color Clr;
            public Monk(int X, int Y, Color Clr)
            {
                this.X = X;
                this.Y = Y;
                this.Clr = Clr;
            }

            public Monk Clone()
            {
                return new Monk(X, Y, Clr);
            }
        }

        class Field
        {
            public Monk[] mW = new Monk[8];
            public Monk[] mB = new Monk[8];
            public int ActMonkID = -1;
            public Color ActSide;

            public Monk ActMonk { get { if (ActMonkID == -1)return null; return ActSide == Color.White ? mW[ActMonkID] : mB[ActMonkID]; } }

            public bool IsStartGame = true;

            public Field(Monk[] mW, Monk[] mB, int ActMonkID, Color ActSide, bool IsStartGame)
            {
                this.mW = mW;
                this.mB = mB;
                this.ActMonkID = ActMonkID;
                this.ActSide = ActSide;
                this.IsStartGame = IsStartGame;
            }

            public void ExecuteMove(Point pnt, Color[,] cells)
            {
                ActMonk.X = pnt.X;
                ActMonk.Y = pnt.Y;
                ChangeSide(cells);
            }

            void ChangeSide(Color[,] cells)
            {
                int ind = GetMonkIDByColor(ActSide == Color.Black ? mW : mB, cells[ActMonk.X, ActMonk.Y]);
                ActSide = ActSide == Color.Black ? Color.White : Color.Black;
                ActMonkID = ind;
            }

            public static int GetMonkIDByColor(Monk[] ml, Color clr)
            {
                for (int i = 0; i < 8; i++) if (ml[i].Clr == clr) return i;
                throw new Exception("Не найден монах с цветом " + clr.ToString());
            }

            public Field Clone()
            {
                Monk[] v_mW = new Monk[8];
                Monk[] v_mB = new Monk[8];
                for (int i = 0; i < 8; i++)
                {
                    v_mW[i] = mW[i].Clone();
                    v_mB[i] = mB[i].Clone();
                }
                return new Field(v_mW, v_mB, ActMonkID, ActSide, IsStartGame);
            }

            public bool MoveIsPossable(Monk mnk, int x, int y)
            {
                List<Point> pl = GetPossablePointsActMonk();
                foreach (Point pnt in pl)
                    if (pnt.X == x && pnt.Y == y)
                        return true;
                return false;
            }

            bool CellIdBusy(Monk[] m1, Monk[] m2, int x, int y)
            {
                for (int i = 0; i < 8; i++)
                    if ((m1[i].X == x && m1[i].Y == y) || (m2[i].X == x && m2[i].Y == y)) return true;
                return false;
            }

            public List<Point> GetPossablePointsActMonk()
            {
                List<Point> pl = new List<Point>();
                bool DirectionIsDown = ActSide == Color.White;
                Monk mnk = ActMonk;

                if (ActMonkID == -1) return pl;

                // прямо
                int j = mnk.Y + (DirectionIsDown ? 1 : -1);
                while (j >= 0 && j < 8)
                {
                    if (CellIdBusy(mW, mB, mnk.X, j)) break;
                    else pl.Add(new Point(mnk.X, j));

                    j = j + (DirectionIsDown ? 1 : -1);
                }

                // по диагоналям
                int i = mnk.X - 1;
                j = mnk.Y + (DirectionIsDown ? 1 : -1);
                while (i >= 0 && i < 8 && j >= 0 && j < 8)
                {
                    if (CellIdBusy(mW, mB, i, j)) break;
                    else pl.Add(new Point(i, j));
                    j = j + (DirectionIsDown ? 1 : -1);
                    i -= 1;
                }

                i = mnk.X + 1;
                j = mnk.Y + (DirectionIsDown ? 1 : -1);
                while (i >= 0 && i < 8 && j >= 0 && j < 8)
                {
                    if (CellIdBusy(mW, mB, i, j)) break;
                    else pl.Add(new Point(i, j));
                    j = j + (DirectionIsDown ? 1 : -1);
                    i += 1;
                }

                return pl;
            }

            public bool IsGameOver(out Color WinSide)
            {
                return IsGameOver(mW, mB, ActSide, ActMonk, out WinSide);
            }

            bool IsGameOver(Monk[] mW, Monk[] mB, Color ActSide, Monk ActMonk, out Color WinSide)
            {
                // проверка достижения противоположного края
                for (int i = 0; i < 8; i++)
                {
                    if (mW[i].Y == 7) { WinSide = Color.White; return true; }
                    if (mB[i].Y == 0) { WinSide = Color.Black; return true; }
                }

                // проверка отсутствия хода у текущего игрока
                if (!IsStartGame && GetPossablePointsActMonk().Count == 0)
                {
                    WinSide = ActSide;
                    return true;
                }

                WinSide = Color.Transparent;
                return false;
            }

        }

        // цвета доски и монахов
        Color[] CLR = new Color[8]
            {
                Color.SaddleBrown,
                Color.Green,
                Color.Red,
                Color.Yellow,
                Color.Orchid,
                Color.Aqua,
                Color.Blue,
                Color.OrangeRed
            };

        Color[,] cells = new Color[8, 8];

        Color AISide = Color.White;
        int Level = 2;

        Field Fld = null;
        Field LastPlayerFld = null;

        public Form1()
        {
            InitializeComponent();
            im.Image = new Bitmap(im.Width, im.Height);

            #region *** Заполнение цветов клеток *********
            for (int i = 0; i < 8; i++)
            {
                cells[i, i] = CLR[7];
                cells[7 - i, i] = CLR[0];
            }

            for (int i = 0; i < 4; i++)
            {
                cells[i, i + 4] = CLR[3];
                cells[i + 4, i] = CLR[3];

                cells[3 - i, i] = CLR[4];
                cells[7 - i, i + 4] = CLR[4];
            }

            int x = 1;
            for (int j = 0; j < 8; j++)
            {
                cells[x, j] = CLR[6];
                cells[x, 7 - j] = CLR[1];
                x += 3; if (x > 7) x -= 8;
            }

            x = 2;
            for (int j = 0; j < 8; j++)
            {
                cells[x, j] = CLR[5];
                cells[x, 7 - j] = CLR[2];
                x += 5; if (x > 7) x -= 8;
            }
            #endregion *** Заполнение цветов клеток *********

            btnNewGame_Click(null, null);
        }

        int step = 50;

        void ReBuildField()
        {
            Graphics gr = Graphics.FromImage(im.Image);
            gr.Clear(Color.Black);

            // поле
            for (int i = 0; i < 8; i++)
                for (int j = 0; j < 8; j++)
                {
                    gr.FillRectangle(new SolidBrush(cells[i, j]), i * step + 1, j * step + 1, step - 2, step - 2);
                    //gr.DrawRectangle(Pens.Black, i * step, j * step, step, step);
                }

            // монахи
            for (int i = 0; i < 8; i++)
            {
                DrawMonk(gr, Fld.mW[i], Brushes.White);
                DrawMonk(gr, Fld.mB[i], Brushes.Black);

            }

            // активный монах
            if (Fld.ActMonkID != -1)
            {
                Monk mnk = Fld.ActMonk;
                gr.FillEllipse(Brushes.White, mnk.X * step + 22, mnk.Y * step + 22, step - 44, step - 44);
                gr.DrawEllipse(Pens.Black, mnk.X * step + 22, mnk.Y * step + 22, step - 44, step - 44);
            }

            // возможные ходы
            if (chbxShowPossablePoints.Checked)
            {
                List<Point> pl = Fld.GetPossablePointsActMonk();
                foreach (Point pnt in pl)
                {
                    gr.DrawRectangle(Pens.White, pnt.X * step + 15, pnt.Y * step + 15, step - 30, step - 30);
                    gr.DrawRectangle(Pens.Black, pnt.X * step + 16, pnt.Y * step + 16, step - 30, step - 30);
                }
            }

            gr.Dispose();
            im.Refresh();

            // надпись "Игра окончена"
            Color winSide;
            pnlGameOver.Visible = Fld.IsGameOver(out winSide);
            if (pnlGameOver.Visible)
            {
                lblGameOverWinSide.Text = winSide == Color.White ? "Выиграли белые" : "Выиграли черные";
            }
        }

        void DrawMonk(Graphics Gr, Monk Mnk, Brush Side)
        {
            Gr.FillEllipse(Side, Mnk.X * step + 8, Mnk.Y * step + 8, step - 16, step - 16);
            Gr.FillEllipse(new SolidBrush(Mnk.Clr), Mnk.X * step + 12, Mnk.Y * step + 12, step - 24, step - 24);
            Gr.FillEllipse(new SolidBrush(Color.FromArgb(100, Color.Black)), Mnk.X * step + 12, Mnk.Y * step + 12, step - 24, step - 24);
            Gr.FillEllipse(new SolidBrush(Mnk.Clr), Mnk.X * step + 18, Mnk.Y * step + 18, step - 36, step - 36);
        }

        private void btnNewGame_Click(object sender, EventArgs e)
        {
            Monk[] mW = new Monk[8];
            Monk[] mB = new Monk[8];
            for (int i = 0; i < 8; i++)
            {
                mW[i] = new Monk(i, 0, CLR[7 - i]);
                mB[i] = new Monk(i, 7, CLR[i]);
            }

            Fld = new Field(mW, mB, -1, Color.Black, true);
            btnUndoLastMove.Enabled = false;
            ReBuildField();
        }

        private void im_MouseDown(object sender, MouseEventArgs e)
        {
            int x = e.X / step;
            int y = e.Y / step;
            if (x < 0 || y < 0 || x > 7 || y > 7) return;

            // если игра только стартует, выбор активного черного монаха или первого хода
            if (Fld.IsStartGame)
            {
                for (int i = 0; i < 8; i++)
                    if (Fld.mB[i].X == x && Fld.mB[i].Y == y)
                    {
                        Fld.ActMonkID = i;
                        ReBuildField();
                        return;
                    }
            }

            // выбор хода
            if (Fld.ActMonkID != -1)
            {
                if (Fld.MoveIsPossable(Fld.ActMonk, x, y))
                {
                    LastPlayerFld = Fld.Clone();
                    Fld.IsStartGame = false;
                    ExecuteMove(new Point(x, y));
                    btnUndoLastMove.Enabled = true;
                }
            }
        }

        void ExecuteMove(Point pnt)
        {
            Fld.ExecuteMove(pnt, cells);
            Color winSide;
            if (!Fld.IsGameOver(out winSide))
            {
                if (Fld.ActSide == AISide) dtAIMove = DateTime.Now.AddSeconds(1);
            }
            ReBuildField();
        }

        Point AI_NextMove(int DifficultyLevel)
        {
            bool DirectionIsDown = Fld.ActSide == Color.White;
            Monk mnk = Fld.ActMonk;
            Point ret = new Point();

            // получение возможных ходов
            List<Point> pl = Fld.GetPossablePointsActMonk();

            // поиск самого дальнего по Y хода
            if (DifficultyLevel == 1)
            {
                // сортируем так, чтобы вначале оказались клетки с наибольшей дальностью
                if (DirectionIsDown)
                {
                    pl.Sort(delegate(Point pnt1, Point pnt2) { return pnt2.Y.CompareTo(pnt1.Y); });
                }
                else
                {
                    pl.Sort(delegate(Point pnt1, Point pnt2) { return pnt1.Y.CompareTo(pnt2.Y); });
                }
                return pl[0];
            }

            if (DifficultyLevel == 2)
            {
                return GetNextMove3(Fld);
            }


            throw new Exception("Не найден алгоритм для уровня сложности " + DifficultyLevel.ToString());
        }

        Point GetNextMove3(Field Fld, int DeepLev, out int DeepLoose)
        {
            // получение возможных ходов
            List<Point> pl = Fld.GetPossablePointsActMonk();

            bool DirectionIsDown = Fld.ActSide == Color.White;
            // сортируем так, чтобы вначале оказались клетки с наибольшей дальностью
            if (DirectionIsDown)
            {
                pl.Sort(delegate(Point pnt1, Point pnt2) { return pnt2.Y.CompareTo(pnt1.Y); });
            }
            else
            {
                pl.Sort(delegate(Point pnt1, Point pnt2) { return pnt1.Y.CompareTo(pnt2.Y); });
            }

            // проссчет возможных ходов
            int[] dpLevL = new int[pl.Count]; // список глубин проигрыша для каждой точки (выбрана будет точка с самым маленьким уровнем)
            for (int p = 0; p < pl.Count; p++)
            {
                Point pnt = pl[p];

                // клон поля
                Field v_fld = Fld.Clone();
                // виртуальный ход
                v_fld.ExecuteMove(pnt, cells);

                // проверка на победу (если победа, то оно)
                // если поражение, переход к следующей
                Color winSide;
                if (v_fld.IsGameOver(out winSide))
                {
                    if (winSide == AISide)
                    {
                        DeepLoose = -1;
                        return pnt;
                    }
                    else
                    {
                        dpLevL[p] = DeepLev;
                        continue;
                    }
                }

                // просмотр возможных ходов противника
                // если хотя бы 1 ход противника ведет его к победе
                List<Point> plEn = v_fld.GetPossablePointsActMonk();
                bool bEnemyWin = false;
                foreach (Point pntEn in plEn)
                {
                    // клон поля
                    Field v_fldEn = v_fld.Clone();
                    // виртуальный ход
                    v_fldEn.ExecuteMove(pntEn, cells);

                    // если этим ходом противник выигрывает
                    if (v_fldEn.IsGameOver(out winSide))
                    {
                        if (winSide != AISide)
                        {
                            bEnemyWin = true;
                            break;
                        }
                    }
                }
                // если противник этим ходом не выигрывает
                if (!bEnemyWin)
                {
                    // если уровень вложенности <=1, возвращаем этот ход
                    if (DeepLev <= 1) { DeepLoose = -1; return pnt; }
                    // иначе проверяем все возможные ходы противника, пытаясь сходить в ответ на них
                    else
                    {
                        // глубина проигрыша (выбрется самый большой. Исходя из того, что противник абсолютно умен и выберет именно этот ход)
                        int maxDpLev = -1;
                        for (int i = 0; i < plEn.Count; i++)
                        {
                            // клон поля
                            Field v_fldEn = v_fld.Clone();
                            // виртуальный ход противника
                            v_fldEn.ExecuteMove(plEn[i], cells);
                            // виртуальный ответный ход AI
                            int dpLev;
                            Point pnt2 = GetNextMove3(v_fldEn, DeepLev - 1, out dpLev);
                            if (maxDpLev < dpLev) maxDpLev = dpLev;
                        }

                        // если хотя бы 1 ход противника ведет к проигрышу, ход неудачен
                        // возвращаем, на каком уровне ход оказался проигрышным
                        if (maxDpLev == int.MaxValue) { DeepLoose = maxDpLev; return pnt; }
                    }
                }
            }

            // поиск хода с минимальным уровнем проигрыша (в идеале, -1. То есть без проигрыша)
            for()

            // если проссчет не удался (все ходы проигрышны), выбираем любой ход
            DeepLoose = DeepLev;
            return pl[0];
        }

        private void chbxShowPossablePoints_CheckedChanged(object sender, EventArgs e)
        {
            ReBuildField();
        }

        DateTime dtAIMove = DateTime.MaxValue;
        private void tmrMain_Tick(object sender, EventArgs e)
        {
            if (Fld.ActSide == AISide && DateTime.Now >= dtAIMove)
            {
                dtAIMove = DateTime.MaxValue;
                Point pnt = AI_NextMove(Level);
                ExecuteMove(pnt);
            }
        }

        private void btnUndoLastMove_Click(object sender, EventArgs e)
        {
            Fld = LastPlayerFld;
            ReBuildField();
            btnUndoLastMove.Enabled = false;
        }

    }
}
